{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Partitioning III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: palindromePartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割回文串 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由小写字母组成的字符串&nbsp;<code>s</code>，和一个整数&nbsp;<code>k</code>。</p>\n",
    "\n",
    "<p>请你按下面的要求分割字符串：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>首先，你可以将&nbsp;<code>s</code>&nbsp;中的部分字符修改为其他的小写英文字母。</li>\n",
    "\t<li>接着，你需要把&nbsp;<code>s</code>&nbsp;分割成&nbsp;<code>k</code>&nbsp;个非空且不相交的子串，并且每个子串都是回文串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回以这种方式分割字符串所需修改的最少字符数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;abc&quot;, k = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>你可以把字符串分割成 &quot;ab&quot; 和 &quot;c&quot;，并修改 &quot;ab&quot; 中的 1 个字符，将它变成回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aabbc&quot;, k = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>你可以把字符串分割成 &quot;aa&quot;、&quot;bb&quot; 和 &quot;c&quot;，它们都是回文串。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;leetcode&quot;, k = 8\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code>&nbsp;中只含有小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-partitioning-iii](https://leetcode.cn/problems/palindrome-partitioning-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-partitioning-iii](https://leetcode.cn/problems/palindrome-partitioning-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n2', '\"aabbc\"\\n3', '\"leetcode\"\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp[i][i+1] = 1 if s[i] != s[i+1] else 0\n",
    "            for j in range(i+2, n):\n",
    "                dp[i][j] = dp[i+1][j-1] + (1 if s[i] != s[j] else 0)\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = dp[0][i]\n",
    "        \n",
    "        for j in range(k-1):\n",
    "            for i in range(n-1, j, -1):\n",
    "                f[i] = min(f[x] + dp[x+1][i] for x in range(j, i))\n",
    "            \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            dp[i][i+1] = 1 if s[i] != s[i+1] else 0\n",
    "            for j in range(i+2, n):\n",
    "                dp[i][j] = dp[i+1][j-1] + (1 if s[i] != s[j] else 0)\n",
    "        \n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[i] = dp[0][i]\n",
    "        \n",
    "        for j in range(k - 1):\n",
    "            for i in range(n-1, j-1, -1):\n",
    "                t = inf\n",
    "                for x in range(i):\n",
    "                    t = min(t, f[x] + dp[x+1][i])\n",
    "                f[i] = t\n",
    "            \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "划分型DP\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        change = [[0] * n for i in range(n)] \n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                change[i][j] = change[i+1][j-1] if i+1 <= j-1 else 0\n",
    "                if s[i] != s[j]:\n",
    "                    change[i][j] += 1\n",
    "\n",
    "        dp = change[0]\n",
    "\n",
    "        for p in range(1, k):\n",
    "            for j in range(n-1, p-1, -1):\n",
    "                dp[j] = inf\n",
    "                for i in range(p, j+1):\n",
    "                    dp[j] = min(dp[j], dp[i-1] + change[i][j])\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        def cost(l, r):\n",
    "            ret, i, j = 0, l, r\n",
    "            while i < j:\n",
    "                ret += (0 if s[i] == s[j] else 1)\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [[inf] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                if j == 1:\n",
    "                    f[i][j] = cost(0, i - 1)\n",
    "                else:\n",
    "                    for i0 in range(j-1, i):\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))\n",
    "        return f[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        # 预处理f[i][j]表示把[i..j]变为回文串的最少修改字符数，之后再跑一个dp枚举分割位置\n",
    "        # f[i][i] = 0\n",
    "        # f[i][i+1] = 1 if s[i] != s[i+1] else 0\n",
    "        # f[i][j] = f[i+1][j-1] + 1 if s[i] != s[j] else f[i+1][j-1]\n",
    "        # i倒序枚举，j正序枚举\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1, n):\n",
    "                f[i][j] = f[i+1][j-1] + 1 if s[i] != s[j] else f[i+1][j-1]\n",
    "        # @cache\n",
    "        # def dfs(i, k): # [0..i]\n",
    "        #     # i不作为base case, 因为随着不断分割，k总是会到1\n",
    "        #     # k为什么是1而不是0，因为把字符串分为k段需要k-1次切割\n",
    "        #     if k == 1: \n",
    "        #         return f[0][i] \n",
    "        #     res = inf\n",
    "        #     for j in range(i):\n",
    "        #         res = min(res, dfs(j, k-1) + f[j+1][i])  # [0..i] = [0..j] + [j+1..i]\n",
    "        #     return res\n",
    "        # return dfs(n-1, k)\n",
    "        g = [[inf] * (k+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for u in range(1, k+1):\n",
    "                if u == 1:\n",
    "                    g[i][u] = f[0][i]\n",
    "                else:\n",
    "                    for j in range(i):\n",
    "                        g[i][u] = min(g[i][u], g[j][u-1] + f[j+1][i])\n",
    "        return g[n-1][k]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        if k>=len(s):\n",
    "            return 0\n",
    "\n",
    "        # f[i][j] = min(f[i0][j-1], cost(S, i0+1, i))\n",
    "        def cost(l, r):\n",
    "            ret, i, j = 0, l, r\n",
    "            while i < j:\n",
    "                ret += (0 if s[i] == s[j] else 1)\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "\n",
    "        n = len(s)\n",
    "        f = [[10**9 for _ in range(k+1)] for _ in range(n+1)]\n",
    "\n",
    "        f[0][0] = 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, min(i, k)+1):\n",
    "                if j==1:\n",
    "                    f[i][j] = cost(0,i-1)\n",
    "                else:\n",
    "                    for i0 in range(j - 1, i):\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))\n",
    "        \n",
    "        return f[n][k]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # 计算子串s[l...r]变成回文需要的最少修改次数\n",
    "        def cost(l: int, r: int) -> int:\n",
    "            changes = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    changes += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return changes\n",
    "\n",
    "        # 初始化动态规划数组\n",
    "        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                for m in range(i):\n",
    "                    dp[i][j] = min(dp[i][j], dp[m][j-1] + cost(m, i-1))\n",
    "\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "划分型DP\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        change = [[0] * n for i in range(n)] \n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                change[i][j] = change[i+1][j-1] if i+1 <= j-1 else 0\n",
    "                if s[i] != s[j]:\n",
    "                    change[i][j] += 1\n",
    "\n",
    "\n",
    "        dp = [[inf] * n for _ in range(k)]\n",
    "        dp[0] = change[0]\n",
    "\n",
    "        for p in range(1, k):\n",
    "            for j in range(p, n):\n",
    "                for i in range(p, j+1):\n",
    "                    dp[p][j] = min(dp[p][j], dp[p-1][i-1] + change[i][j])\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        第I类区间DP\n",
    "    '''\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        N = len(s)\n",
    "        K = k\n",
    "        s = \" \" + s\n",
    "        # dp[i][k]表示将s[1:i]分成k个回文子串的最小修改字符数\n",
    "        dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]\n",
    "        def calc(j: int, i: int) -> int:\n",
    "            cnt = 0\n",
    "            while j < i:\n",
    "                cnt += s[j] != s[i]\n",
    "                j += 1\n",
    "                i -= 1\n",
    "            return cnt\n",
    "        # step1: 初始化k=1\n",
    "        for i in range(1, N + 1):\n",
    "            dp[i][1] = calc(1, i)\n",
    "        # step2: 写出第I类区间DP框架\n",
    "        for i in range(1, N + 1):\n",
    "            for k in range(2, min(i, K) + 1):\n",
    "                dp[i][k] = 0x3f\n",
    "                for j in range(i, k - 1, -1):\n",
    "                    dp[i][k] = min(dp[i][k], dp[j - 1][k - 1] + calc(j, i)) \n",
    "        return dp[N][K]\n",
    "                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        # dp states transition\n",
    "        # dp[i][j] -> 前i个字符，分割成j个非空不相交的字符串，需要改的字符数\n",
    "        # dp[i][j] = min(dp[i0][j-1] + cost(s, i0+1, i))\n",
    "        # cost(s, i0+1, i)是要把从i0+1个到第i个字符的字符串改成回文的最小改动数\n",
    "        # 如何求cost? 直接比较tmp 和tmp[::-1]？\n",
    "        # print(s)\n",
    "        # print(k)\n",
    "        def cost(s, i0, i):\n",
    "            s_tmp = s[i0 - 1:i]\n",
    "            s_tmp_reverse = s_tmp[::-1]\n",
    "            res = 0\n",
    "            for j in range(len(s_tmp)):\n",
    "                if s_tmp[j] != s_tmp_reverse[j]:\n",
    "                    res += 1\n",
    "            return int(res/2)\n",
    "        dp = [[0 for _ in range(k + 1)] for _ in range(len(s) + 1)]\n",
    "        for i in range(1, len(s)+1):\n",
    "            for j in range(1, min(i+1,k+1)):\n",
    "                if j == 1:\n",
    "                    dp[i][j] = cost(s, 1, i)\n",
    "                elif j == i:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    arr = []\n",
    "                    for i0 in range(j-1, i):\n",
    "                        arr.append(dp[i0][j-1] + cost(s, i0+1, i))\n",
    "                    # print(arr)\n",
    "                    dp[i][j] = min(arr)\n",
    "        # print(dp)\n",
    "        return dp[len(s)][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        def cost(l, r):\n",
    "            ret, i, j = 0, l, r\n",
    "            while i < j:\n",
    "                ret += 0 if s[i] == s[j] else 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [[10**9] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                if j == 1:\n",
    "                    f[i][j] = cost(0, i - 1)\n",
    "                else:\n",
    "                    for i0 in range(j - 1, i):\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))\n",
    "        \n",
    "        return f[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        modify=[[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                cnt,t=0,s[i:j+1]\n",
    "                for x in range(len(t)//2):\n",
    "                    cnt+=t[x]!=t[-1-x]\n",
    "                modify[i][j]=cnt\n",
    "        f=[[0]*n for i in range(n)]\n",
    "        f[0]=modify[0]\n",
    "        for i in range(1,k):\n",
    "            for j in range(i,n):\n",
    "                res=inf\n",
    "                for l in range(i,j+1):\n",
    "                    res=min(res,f[i-1][l-1]+modify[l][j])\n",
    "                f[i][j]=res\n",
    "        return f[k-1][n-1]\n",
    "        # @cache\n",
    "        # def dfs(i,j):\n",
    "        #     if i==0:\n",
    "        #         return modify[0][j]\n",
    "        #     res=inf\n",
    "        #     for l in range(i,j+1):\n",
    "        #         res=min(res,dfs(i-1,l-1)+modify[l][j])\n",
    "        #     return res\n",
    "        # return dfs(k-1,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        change = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i+1, n):\n",
    "                change[i][j] = change[i+1][j-1] + (s[i] != s[j])\n",
    "\n",
    "        dp = [[n] * (k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(n):\n",
    "            for kk in range(1, k+1):\n",
    "                dp[i+1][kk] = min(dp[j][kk-1] + change[j][i] for j in range(i+1))\n",
    "        return dp[n][k]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        l = len(s)\n",
    "        # dp - 以i为结尾分成j组所需的最少修改次数\n",
    "        dp = [[0] * (k + 1) for _ in range(l + 1)]\n",
    "\n",
    "        def count(word):\n",
    "            res = 0\n",
    "            w = word[::-1]\n",
    "            for i in range(len(word)):\n",
    "                if word[i] != w[i]:\n",
    "                    res += 1\n",
    "            return res // 2\n",
    "        \n",
    "        for i in range(1, l + 1):\n",
    "            dp[i][1] = count(s[:i])\n",
    "\n",
    "        for i in range(1, l + 1):\n",
    "            for j in range(2, min(i, k) + 1):\n",
    "                dp[i][j] = float('inf')\n",
    "                for t in range(i, -1, -1):\n",
    "                    if t < j:\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], dp[t - 1][j - 1] + count(s[t - 1:i]))\n",
    "\n",
    "        return dp[l][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self, start, end):\n",
    "        num = 0\n",
    "        while start < end:\n",
    "            if self.s[start] != self.s[end]:\n",
    "                num += 1\n",
    "            start += 1\n",
    "            end -= 1\n",
    "\n",
    "        return num\n",
    "\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        self.s = s\n",
    "        dp = [[i] * (k + 1) for i in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, k + 1):\n",
    "                if i < j:\n",
    "                    continue\n",
    "                elif j == 1:\n",
    "                    dp[i][j] = self.count(0, i - 1)\n",
    "                elif i == j:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    minCount = dp[i][j]\n",
    "                    for t in range(j, i + 1):\n",
    "                        minCount = min(minCount, dp[t - 1][j - 1] + self.count(t - 1, i - 1))\n",
    "                    dp[i][j] = minCount\n",
    "\n",
    "        return dp[-1][-1]\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        s_len = len(s)\n",
    "        # dp - 以i为结尾分成j组所需的最少修改次数\n",
    "        dp = [[0] * (k + 1) for _ in range(s_len + 1)]\n",
    "\n",
    "        # cost - 把s[l:r]变成回文需要的最少修改次数\n",
    "        # 这一步相当于预处理\n",
    "        cost = [[0] * (s_len + 1) for _ in range(s_len + 1)]\n",
    "        for r in range(1, s_len + 1):\n",
    "            for l in range(r - 1, 0, -1):\n",
    "                if s[r - 1] == s[l - 1]:\n",
    "                    cost[r][l] = cost[r - 1][l + 1]\n",
    "                else:\n",
    "                    cost[r][l] =cost[r - 1][l + 1] + 1\n",
    "        \n",
    "        # 当j为0时表示分成0组, 没有意义\n",
    "        # 所以j从1开始\n",
    "        for i in range(1, s_len + 1):\n",
    "            dp[i][1] = cost[i][1]\n",
    "\n",
    "        for i in range(1, s_len + 1):\n",
    "            for j in range(2, min(i, k) + 1):\n",
    "                dp[i][j] = float('inf')\n",
    "                for t in range(i, -1, -1):\n",
    "                    if t < j:  # 剩下的数字不够分成j组, 所以break\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], dp[t - 1][j - 1] + cost[i][t])\n",
    "\n",
    "        return dp[s_len][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        def modify(l,r):\n",
    "            cnt = 0\n",
    "            while l<r:\n",
    "                cnt += s[l]!=s[r]\n",
    "                l+=1\n",
    "                r-=1\n",
    "\n",
    "            return cnt\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if j == 1:\n",
    "               return modify(0,i)\n",
    "            ans = inf\n",
    "\n",
    "            for L in range(j-1,i+1):\n",
    "                ans = min(ans,dfs(L-1,j-1)+modify(L,i))\n",
    "\n",
    "            return ans \n",
    "\n",
    "        return dfs(n-1,k)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\r\n",
    "        n = len(s)\r\n",
    "        reversed_s = s[::-1]\r\n",
    "        f = [[float('inf')]*(n+1) for _ in range(n+1)]\r\n",
    "        edits = [[0]*(n+1) for _ in range(n+1)]\r\n",
    "        for i in range(n-1):\r\n",
    "            if bool(s[i] != s[i+1]):\r\n",
    "                edits[i][i+1] = 1\r\n",
    "        for l in range(3, n+1):\r\n",
    "            for i in range(n-l+1):\r\n",
    "                j = i+l-1\r\n",
    "                edits[i][j] = edits[i+1][j-1] + int(s[i] != s[j])\r\n",
    "        for i in range(n):\r\n",
    "            f[i][1] = edits[0][i]\r\n",
    "        for l in range(2, k+1):\r\n",
    "            for i in range(l-1, n):\r\n",
    "                for j in range(l-2, i):\r\n",
    "                    f[i][l] = min(f[i][l], f[j][l-1]+edits[j+1][i])\r\n",
    "\r\n",
    "        return f[n-1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        def check(l,r):\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "        # dp[i][j]表示分割前i个字符串为j个非空且不相交的子串所需修改的最少字符数\n",
    "        # dp[i][j] = dp[ni][j-1]+check(ni,i-1) for ni in range(j-1,i)\n",
    "        n = len(s)\n",
    "        dp = [[inf]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,k+1):\n",
    "                for ni in range(j-1,i):\n",
    "                    if j == 1:\n",
    "                        dp[i][j] = check(0,i-1)\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i][j],dp[ni][j-1]+check(ni,i-1)) \n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        def check(l,r):\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "\n",
    "        # dp[i][j]表示分割前i个字符串分割为j个非空且不相交的回文串最少需要修改的字符数\n",
    "        # dp[i][j] = min(dp[next][j-1]+check(s,next,i) for next in range(j-1,i))\n",
    "        n = len(s)\n",
    "        dp = [[inf]*(k+1) for _ in range(n+1)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,min(k,i)+1):\n",
    "                if j == 1:\n",
    "                    dp[i][j] = check(0,i-1)\n",
    "                else:\n",
    "                    for nest in range(j-1,i):\n",
    "                        dp[i][j] = min(dp[nest][j-1]+check(nest,i-1),dp[i][j])\n",
    "        return dp[n][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for end in range(n):\n",
    "            for start in range(end):\n",
    "                if end == start+1:\n",
    "                    dp[start][end] = int(s[start] != s[end])\n",
    "                else:\n",
    "                    dp[start][end] = int(s[start] != s[end]) + dp[start+1][end-1]\n",
    "        dp2 = [[100]*(k+1) for _ in range(n+1)]\n",
    "        dp2[-1][-1] = 0\n",
    "        for now in range(n-1, -1, -1):\n",
    "            for count in range(k-1, -1, -1):\n",
    "                for end in range(now, n):\n",
    "                    dp2[now][count] = min(dp[now][end] + dp2[end+1][count+1], dp2[now][count])\n",
    "        return dp2[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        def helper(l, r):\n",
    "            cnt = 0               \n",
    "            while l < r:\n",
    "                cnt += s[l] != s[r]                \n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return cnt\n",
    "        @cache\n",
    "        def dfs(i , k):\n",
    "            if i < 0 : return 0\n",
    "            if i == k - 1: return 0\n",
    "            if k == 1 : return helper(0 , i)\n",
    "            res = inf\n",
    "            for j in range(k - 2, i):                              \n",
    "                res = min(res , dfs(j , k - 1) + helper(j + 1 , i))\n",
    "            return res\n",
    "        return dfs(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        if k>=len(s):\n",
    "            return 0\n",
    "\n",
    "        # f[i][j] = min(f[i0][j-1], cost(S, i0+1, i))\n",
    "        def cost(l, r):\n",
    "            ret, i, j = 0, l, r\n",
    "            while i < j:\n",
    "                ret += (0 if s[i] == s[j] else 1)\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "\n",
    "        n = len(s)\n",
    "        f = [[10**9 for _ in range(k+1)] for _ in range(n+1)]\n",
    "\n",
    "        f[0][0] = 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, min(i, k)+1):\n",
    "                if j==1:\n",
    "                    f[i][j] = cost(0,i-1)\n",
    "                else:\n",
    "                    for i0 in range(j - 1, i):\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))\n",
    "        \n",
    "        return f[n][k]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        dp = [[10**9] * (k + 1) for _ in range(len(s))]#i j 以i结尾分成j份的最小修改\n",
    "        change = [[0] * len(s) for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                change[i][j] = self.check(s, i, j)\n",
    "        #dp[i][j] = min(dp[i-k][j-1] + change[k][i])\n",
    "        #dp[0][1] = 0\n",
    "        \n",
    "        for i in range(len(s)):\n",
    "            dp[i][1] = change[0][i]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(2, min(i + 1, k) + 1):\n",
    "                for x in range(i):\n",
    "                    dp[i][j] = min(dp[i][j], dp[x][j-1] + change[x + 1][i])\n",
    "            #print(dp[i])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "    def check(self, s, start, end):\n",
    "        res = 0\n",
    "        while start < end:\n",
    "            if s[start] != s[end]:\n",
    "                res += 1\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                left, right = i, j \n",
    "                while left < right:\n",
    "                    if s[left] != s[right]:\n",
    "                        cost[i][j] += 1\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "\n",
    "        f = [[0] * k for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = cost[0][i]\n",
    "            for j in range(1, min(i+1, k)):\n",
    "                f[i][j] = min([f[p][j-1] + cost[p+1][i] for p in range(j-1, i)])\n",
    "        return f[n-1][k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        def get_modify(string):\n",
    "            n = len(string)\n",
    "            res = 0\n",
    "            i,j = 0,n-1\n",
    "            while(i<j):\n",
    "                res += string[i] != string[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return res\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                dp[i][j] = get_modify(s[i:j+1])\n",
    "        print(dp)\n",
    "        \n",
    "        def dfs(i,j):\n",
    "            if i == 0:\n",
    "                return dp[0][j]\n",
    "            return min([dfs(i-1,L-1)+dp[L][j] for L in range(i,j+1)])\n",
    "        \n",
    "        f = dp[0]\n",
    "        for i in range(1,k):\n",
    "            for j in range(n-1,i-1,-1):\n",
    "                f[j] = min([f[L-1]+dp[L][j] for L in range(i,j+1)])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        if len(s) == k:\n",
    "            return 0\n",
    "\n",
    "        def check(l, r):\n",
    "            ans = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    ans += 1\n",
    "                \n",
    "                l += 1\n",
    "                r -= 1\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(i, num):\n",
    "            if num == 1:\n",
    "                return check(0,i)\n",
    "            \n",
    "            ans = float('inf')\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if j + 1 < num - 1:\n",
    "                    break\n",
    "\n",
    "                ans = min(ans, dp(j, num - 1) + check(j + 1, i))\n",
    "\n",
    "            \n",
    "            return ans\n",
    "\n",
    "    \n",
    "\n",
    "        return dp(len(s) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        l = len(s)\n",
    "        # dp - 以i为结尾分成j组所需的最少修改次数\n",
    "        dp = [[0] * (k + 1) for _ in range(l + 1)]\n",
    "\n",
    "        cost = [[0] * (l + 1) for _ in range(l + 1)]\n",
    "        for i in range(1, l + 1):\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                if s[i - 1] == s[j - 1]:\n",
    "                    cost[i][j] = cost[i - 1][j + 1]\n",
    "                else:\n",
    "                    cost[i][j] =cost[i - 1][j + 1] + 1\n",
    "\n",
    "        def count(word):\n",
    "            res = 0\n",
    "            w = word[::-1]\n",
    "            for i in range(len(word)):\n",
    "                if word[i] != w[i]:\n",
    "                    res += 1\n",
    "            return res // 2\n",
    "        \n",
    "        for i in range(1, l + 1):\n",
    "            dp[i][1] = cost[i][1]\n",
    "\n",
    "        for i in range(1, l + 1):\n",
    "            for j in range(2, min(i, k) + 1):\n",
    "                dp[i][j] = float('inf')\n",
    "                for t in range(i, -1, -1):\n",
    "                    if t < j:\n",
    "                        break\n",
    "                    dp[i][j] = min(dp[i][j], dp[t - 1][j - 1] + cost[i][t])\n",
    "\n",
    "        return dp[l][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        N = len(s)\n",
    "        f = [ [ float(\"inf\") for j in range(k+1) ] for i in range(N+1) ]\n",
    "        ct = [ [ 0 for _ in range(N+1) ] for _ in range(N+1) ]\n",
    "\n",
    "        for i in range(N, 0, -1):\n",
    "            for j in range(i+1, N+1):\n",
    "                if s[i-1] == s[j-1]:\n",
    "                    ct[i][j] = ct[i+1][j-1]\n",
    "                else:\n",
    "                    ct[i][j] = ct[i+1][j-1] + 1\n",
    "        \n",
    "        for i in range(1, N+1):\n",
    "            for j in range(1, min(i, k) + 1):\n",
    "                if j == 1:\n",
    "                    f[i][j] = ct[1][i]\n",
    "                else:\n",
    "                    for m in range(1, i):\n",
    "                        f[i][j] = min(f[i][j], f[m][j-1] + ct[m+1][i])\n",
    "        return f[N][k]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        N = len(s)\n",
    "        f = [ [ float(\"inf\") for j in range(k+1) ] for i in range(N+1) ]\n",
    "        ct = [ [ 0 for _ in range(N+1) ] for _ in range(N+1) ]\n",
    "\n",
    "        for i in range(N, 0, -1):\n",
    "            for j in range(i+1, N+1):\n",
    "                if s[i-1] == s[j-1]:\n",
    "                    ct[i][j] = ct[i+1][j-1]\n",
    "                else:\n",
    "                    ct[i][j] = ct[i+1][j-1] + 1\n",
    "        \n",
    "        for i in range(1, N+1):\n",
    "            for j in range(1, min(i, k) + 1):\n",
    "                if j == 1:\n",
    "                    f[i][j] = ct[1][i]\n",
    "                else:\n",
    "                    for m in range(j-1, i):\n",
    "                        f[i][j] = min(f[i][j], f[m][j-1] + ct[m+1][i])\n",
    "        return f[N][k]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def cost(l, r):\n",
    "            ret, i, j = 0, l, r\n",
    "            while i < j:\n",
    "                ret += 0 if s[i] == s[j] else 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ret\n",
    "        \n",
    "        n = len(s)\n",
    "        f = [[10**9] * (k + 1) for _ in range(n + 1)]\n",
    "        f[0][0] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(k, i) + 1):\n",
    "                if j == 1:\n",
    "                    f[i][j] = cost(0, i - 1)\n",
    "                else:\n",
    "                    for i0 in range(j - 1, i):\n",
    "                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))\n",
    "        \n",
    "        return f[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        cost = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if i+1<n:\n",
    "                j = i+1\n",
    "                cost[i][j] = 1 if s[i] != s[j] else 0\n",
    "            for j in range(i+2, n):\n",
    "                cost[i][j] = cost[i+1][j-1] + int(s[i]!=s[j])\n",
    "\n",
    "        dp = [[inf]*k for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = cost[0][i]\n",
    "            for j in range(1, k):\n",
    "                dp[i+1][j] = min(dp[x][j-1]+cost[x][i] for x in range(i+1))\n",
    "        return dp[n][k-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        def cost(l,r)->int:\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "        # 前i个字符分成j份\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j)->int:\n",
    "            if j == 1:\n",
    "                return cost(0,i)\n",
    "            if i+1 == j:\n",
    "                return 0\n",
    "            if i+1 < j:\n",
    "                return inf\n",
    "            res = inf\n",
    "            for d in range(j-2,i):\n",
    "                res = min(res,dfs(d,j-1)+cost(d+1,i))\n",
    "            return res\n",
    "        return dfs(n-1,k)\n",
    "\n",
    "s = Solution()\n",
    "s.palindromePartition(\"abc\",2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        # dp[i][j] 表示前i个字符，将它分割成j个非空且不相交的回文串，最少需要修改的字符数\n",
    "        # dp[i][j] = min(dp[i0][j-1] + cost(i0, i-1))\n",
    "        # i0表示第j个回文串的起始位置，它前面有0~i0-1共i0个字符，j-1个串，所以dp式为dp[i0][j-1]\n",
    "        # cost(i0, i-1)表示将 i0~i-1 位置的字符串变成回文串，需要最少的修改次数\n",
    "\n",
    "        n = len(s)\n",
    "        # 先计算i~j需要修改成回文字符串需要消耗的修改次数\n",
    "        cost = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                cost[i][j] = cost[i+1][j-1] + (0 if s[i] == s[j] else 1)\n",
    "\n",
    "        dp = [[float(\"inf\") for _ in range(k+1)] for _ in range(n+1)]\n",
    "        dp[0][0] = 0 # 0个字符，不需要修改次数\n",
    "\n",
    "        for i in range(1, n+1): # 前i个字符\n",
    "            # j表示分割成j份，i个字符，最大能分i份，所以有min(k,i)\n",
    "            for j in range(1, min(k,i)+1):\n",
    "\n",
    "                if j == 1: # 只分一份，则只需要看i个字符需要修改几个字符\n",
    "                    dp[i][j] = cost[0][i-1]\n",
    "                else:\n",
    "\n",
    "                    # 遍历第j个回文串的起始位置i0\n",
    "                    # 注意，对于dp[i0][j-1]，表示前i0个字符，分j-1份，j-1的最大值是分i0份，即 i0 >= j-1\n",
    "                    # 所以i0的起始位置是j-1，终止位置是i-1（因为是求前i个字符）\n",
    "                    for i0 in range(j-1, i):\n",
    "                        dp[i][j] = min(dp[i][j], dp[i0][j-1] + cost[i0][i-1])\n",
    "\n",
    "        return dp[n][k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        modify=[[0]*n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                cnt,t=0,s[i:j+1]\n",
    "                for x in range(len(t)//2):\n",
    "                    cnt+=t[x]!=t[-1-x]\n",
    "                modify[i][j]=cnt\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return modify[0][j]\n",
    "            res=inf\n",
    "            for l in range(i,j+1):\n",
    "                res=min(res,dfs(i-1,l-1)+modify[l][j])\n",
    "            return res\n",
    "        return dfs(k-1,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        if len(s) == k:\n",
    "            return 0\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(len(dp) - 2, -1, -1):\n",
    "            for j in range(i + 1, len(dp[0])):\n",
    "                dp[i][j] = (dp[i + 1][j - 1] if i + 1 <= j - 1 else 0) + (s[i] != s[j])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, num):\n",
    "            if num == 1:\n",
    "                return dp[0][i]\n",
    "            \n",
    "            ans = float('inf')\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if j + 1 < num - 1:\n",
    "                    break\n",
    "\n",
    "                ans = min(ans, dfs(j, num - 1) + dp[j + 1][i])\n",
    "\n",
    "            \n",
    "            return ans\n",
    "\n",
    "    \n",
    "\n",
    "        return dfs(len(s) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        \"\"\"\"\n",
    "            划分型dp \n",
    "        \"\"\"\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        # def modify(l,r):\n",
    "        #     cnt = 0\n",
    "        #     while l<r:\n",
    "        #         cnt += s[l]!=s[r]\n",
    "        #         l+=1\n",
    "        #         r-=1\n",
    "\n",
    "        #     return cnt\n",
    "\n",
    "        cost = [[0]*n for _ in range(n)]\n",
    "\n",
    "        for l  in range(2,n+1):\n",
    "            for i in range(n-l+1):\n",
    "                j =  i +l-1\n",
    "                cost[i][j] = cost[i+1][j-1]+(s[i]!=s[j])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if j == 1:\n",
    "               return cost[0][i]\n",
    "            ans = inf\n",
    "\n",
    "            for L in range(j-1,i+1):\n",
    "                ans = min(ans,dfs(L-1,j-1)+cost[L][i])\n",
    "\n",
    "            return ans \n",
    "\n",
    "        return dfs(n-1,k)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        cost = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                t = s[i:j+ 1]\n",
    "                diff = 0\n",
    "                for l in range(len(t) // 2):\n",
    "                    if t[l] != t[len(t) - 1 - l]:\n",
    "                        diff += 1\n",
    "                cost[i][j] = diff\n",
    "        # print(cost)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return cost[0][j]\n",
    "            \n",
    "            return min(dfs(i - 1, L - 1) + cost[L][j] for L in range(i, j + 1))\n",
    "        \n",
    "        return dfs(k - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[inf]*n for _ in range(k)]\n",
    "\n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            ans=0\n",
    "            while l<r:\n",
    "                if s[l]!=s[r]:\n",
    "                    ans+=1\n",
    "                l+=1\n",
    "                r-=1\n",
    "            return ans\n",
    "        for r in range(n):\n",
    "            dp[0][r]=dfs(0,r)\n",
    "        ans=inf\n",
    "        for p in range(1,k):\n",
    "            for r in range(p,n-(k-p)+1):\n",
    "                for pr in range(p-1,r):  \n",
    "                    dp[p][r]=min(dp[p][r],dp[p-1][pr]+dfs(pr+1,r))\n",
    "        #print(dp)      \n",
    "        return dp[k-1][n-1]\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, rem):\n",
    "            if rem == 0 and i < 0:\n",
    "                return 0\n",
    "            elif rem == 0 and i >= 0:\n",
    "                return inf\n",
    "            elif i == -1:\n",
    "                return inf\n",
    "            res = inf\n",
    "            for start in range(rem - 1, i + 1):\n",
    "                cur, j, k = 0, start, i\n",
    "                while j < k:\n",
    "                    if s[j] != s[k]:\n",
    "                        cur += 1\n",
    "                    j += 1\n",
    "                    k -= 1\n",
    "                res = min(res, dfs(start - 1, rem - 1) + cur)\n",
    "            return res\n",
    "        ans = dfs(len(s) - 1, k)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        cost = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                t = s[i:j+ 1]\n",
    "                diff = 0\n",
    "                for l in range(len(t) // 2):\n",
    "                    if t[l] != t[len(t) - 1 - l]:\n",
    "                        diff += 1\n",
    "                cost[i][j] = diff\n",
    "        # print(cost)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return cost[0][j]\n",
    "            \n",
    "            return min(dfs(i - 1, L - 1) + cost[L][j] for L in range(i, j + 1))\n",
    "        \n",
    "        return dfs(k - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        cost = [[0] * n for _ in range(n)]\n",
    "        for span in range(2, n + 1):\n",
    "            for i in range(n - span + 1):\n",
    "                j = i + span - 1\n",
    "                cost[i][j] = cost[i + 1][j - 1] + (0 if s[i] == s[j] else 1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == 0:\n",
    "                return cost[0][j]\n",
    "            \n",
    "            return min(dfs(i - 1, L - 1) + cost[L][j] for L in range(i, j + 1))\n",
    "        \n",
    "        return dfs(k - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        L = len(s)\n",
    "        # 定义dp数组, 其中dp[i][j]为s[i:j + 1]变为回文串需要修改的的最少字符数\n",
    "        # 当i == j时, dp[i][j] = 0 (单个字符必然是回文的)\n",
    "        dp = [[0] * L for i in range(L)]\n",
    "        # 转移方程: dp[i][j] = dp[i + 1][j - 1] + (s[i] != s[j]) (参考最长回文子串)\n",
    "\n",
    "        for j in range(L):\n",
    "            for i in range(j):\n",
    "                v = int(s[i] != s[j])\n",
    "                if j - i < 3:\n",
    "                    dp[i][j] = v\n",
    "                else:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + v\n",
    "        # 这样我们得到了一个辅助数组,可以快速查询s的某个子串变为回文串需要修改的的最少字符数\n",
    "\n",
    "        # 记忆化搜索\n",
    "        # 定义函数dfs(idx, sur): 返回需要分割sur个字符串时, s[idx:]所需修改的最少字符数。\n",
    "        @cache\n",
    "        def dfs(idx, sur):\n",
    "            # base case: 当只需要分割成1个子串时,只能把当前字符串变为回文串\n",
    "            if sur == 1: return dp[idx][L - 1] \n",
    "            ans = inf\n",
    "            # 枚举分割点取最小值即可, 分割点不能太靠后, 要始终保证s[idx:]的字符数量大于等于sur\n",
    "            # 不然根本无法分割成sur个子串\n",
    "            for i in range(idx, L - sur + 1):\n",
    "                ans = min(ans, dp[idx][i] + dfs(i + 1, sur - 1))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        K = k\n",
    "        cost = [[0 for _ in range(n)] for _ in range(n)]  \n",
    "        # for i in range(n):\n",
    "        #     cost[i][i] = 0\n",
    "        for l in range(2, n + 1):\n",
    "            for i in range(n - l + 1):\n",
    "                j = i + l - 1\n",
    "                cost[i][j] = cost[i+1][j-1] if s[i] == s[j] else cost[i+1][j-1] + 1  # 注意这里不要写错为i-1,j+1\n",
    "        # dp[i][k]表示把前i个字符分成k份的最小cost\n",
    "        dp = [[float(\"inf\") for _ in range(K + 1)] for _ in range(n)]\n",
    "        # dp = [[0 for _ in range(K+1)] for _ in range(n)]\n",
    "        # dp[0][0] = 0\n",
    "        # for i in range(n):\n",
    "        for i in range(n):   # 注意i是否取到0\n",
    "            # for k in range(1, K + 1):\n",
    "            dp[i][1] = cost[0][i]\n",
    "            # for k in range(2, min(K, i) + 1):  # k至少要取2，而不是1\n",
    "            for k in range(2, K + 1):\n",
    "                # for j in range(k-1, i):   # j表示将前j个字符分成k-1份，因此j必须大于等于k-1（不采取这种思路）\n",
    "                for j in range(i): \n",
    "                    # dp[i][1] = cost[0][i] # 这句话放在循环外边\n",
    "                    dp[i][k] = min(\n",
    "                        dp[i][k], \n",
    "                        dp[j][k-1] + cost[j+1][i]\n",
    "                    )\n",
    "        print(dp)\n",
    "        return dp[n-1][K]\n",
    "\n",
    "\n",
    "'''\n",
    "        n = len(s)\n",
    "        cost = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     cost[i][i] = 0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        for length in range(2, n + 1):  # 这里易错！！length是可以取到n的\n",
    "            for i in range(0, n - length + 1):\n",
    "                j = i + length - 1\n",
    "                cost[i][j] = cost[i+1][j-1] if s[i] == s[j] else cost[i+1][j-1] + 1\n",
    "        dp = [[0 for _ in range(k+1)] for _ in range(n+1)]\n",
    "        #dp[i][k]: k <= i  , 前i个字符分为k份\n",
    "        dp[1][1] = 1\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for k_i in range(1, k + 1):\n",
    "                for j in range(1, i + 1):   # 这里不要把j定义成分界点坐标，直接将j定义为上一轮前j个点视为k_i-1组，本轮从j+1号点开始到i处作为一组\n",
    "                # 在循环里，dp的初始化过程为：dp[i][1] = cost[0][i]，表示前i个化成一组，相当于前i个直接变换回文的cost\n",
    "                    # dp[i][k_i] = dp[i - j][k_i - 1] + cost[i-j][j]\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 将s修改为回文串需要的次数\n",
    "def get_modify(s):\n",
    "    return sum(s[i]!=s[-1-i] for i in range(len(s)//2))\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        modify = [[0]*n for _ in range(n)]\n",
    "        for l in range(n-1):\n",
    "            for r in range(l+1,n):\n",
    "                modify[l][r] = get_modify(s[l:r+1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return modify[0][j]\n",
    "            return min(dfs(i-1,L-1)+modify[L][j] for L in range(i,j+1))\n",
    "        return dfs(k-1,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        @lru_cache(None)\n",
    "        def cost(l,r)->int:\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "        # 前i个字符分成j份\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j)->int:\n",
    "            if j == 1:\n",
    "                return cost(0,i)\n",
    "            if i+1 == j:\n",
    "                return 0\n",
    "            if i+1 < j:\n",
    "                return inf\n",
    "            res = inf\n",
    "            for d in range(j-2,i):\n",
    "                res = min(res,dfs(d,j-1)+cost(d+1,i))\n",
    "            return res\n",
    "        return dfs(n-1,k)\n",
    "\n",
    "s = Solution()\n",
    "s.palindromePartition(\"abc\",2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def count(beg, end):\n",
    "            if beg >= end:\n",
    "                return 0\n",
    "            else:\n",
    "                return (s[beg] != s[end]) + count(beg+1, end-1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def partition(i, k):\n",
    "            if k == 1:\n",
    "                return count(0,i)\n",
    "\n",
    "            return min(partition(j, k-1) + count(j+1, i) for j in range(k-2, i))\n",
    "\n",
    "        return partition(len(s)-1, k)\n",
    "           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def count(beg, end):\n",
    "            if beg >= end:\n",
    "                return 0\n",
    "            else:\n",
    "                return (s[beg] != s[end]) + count(beg+1, end-1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def partition(i, k):\n",
    "            if k == 1:\n",
    "                return count(0,i)\n",
    "\n",
    "            return min(partition(j, k-1) + count(j+1, i) for j in range(k-2, i))\n",
    "\n",
    "        return partition(len(s)-1, k)\n",
    "           \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int: \n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                l, r = i, j\n",
    "                while l < r:\n",
    "                    if s[l] != s[r]: f[i][j] += 1\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "        g = [[n] * (k + 1) for _ in range(n)]\n",
    "        for i in range(n): \n",
    "            g[i][0] = 0\n",
    "            g[i][1] = f[0][i]\n",
    "        for i in range(n):\n",
    "            for j in range(2, k + 1):\n",
    "                for l in range(j - 2,i):\n",
    "                    g[i][j] = min(g[l][j - 1] + f[l + 1][i], g[i][j])\n",
    "                    if i == n - 1: print(j, l, g[i][j], g[l][j - 1], f[l + 1][i])\n",
    "        \n",
    "        return g[n - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        def cost(i, j):\n",
    "            l, r = i, j\n",
    "            res = 0\n",
    "            while l < r:\n",
    "                if s[l] != s[r]: \n",
    "                    res += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return res\n",
    "        @cache\n",
    "        def dfs(pos, left):\n",
    "            if pos == n:\n",
    "                if left == 0: return 0\n",
    "                return inf\n",
    "            res = inf\n",
    "            for i in range(pos, n):\n",
    "                res = min(res, cost(pos, i) + dfs(i + 1, left - 1))\n",
    "            return res\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\r\n",
    "        n = len(s) \r\n",
    "        @cache\r\n",
    "        def cost(i, j):\r\n",
    "            if i >= j: return 0  \r\n",
    "            return cost(i + 1, j - 1) + int(s[i] != s[j])\r\n",
    "        @cache\r\n",
    "        def dfs(i, k):\r\n",
    "            if k == 1: return cost(0, i - 1)\r\n",
    "            return min(dfs(j, k - 1) + cost(j, i - 1) for j in range(k - 1, i))\r\n",
    "        return dfs(len(s), k) \r\n",
    "\r\n",
    "            \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def cost(start, end):\n",
    "            cur = 0\n",
    "            while start < end:\n",
    "                if s[start] != s[end]:\n",
    "                    cur += 1\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            return cur\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, rem):\n",
    "            if rem == 0 and i < 0:\n",
    "                return 0\n",
    "            elif rem == 0 and i >= 0:\n",
    "                return inf\n",
    "            elif i == -1:\n",
    "                return inf\n",
    "            res = inf\n",
    "            for start in range(rem - 1, i + 1):\n",
    "                cur_cost = cost(start, i)\n",
    "                res = min(res, dfs(start - 1, rem - 1) + cur_cost)\n",
    "            return res\n",
    "        ans = dfs(len(s) - 1, k)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\r\n",
    "        if k == len(s):\r\n",
    "            return 0 \r\n",
    "        # 考虑需要单次划分出尽可能长的回文串\r\n",
    "\r\n",
    "        n = len(s) \r\n",
    "        @cache\r\n",
    "        def cost(i, j):\r\n",
    "            if i >= j:\r\n",
    "                return 0  \r\n",
    "            return cost(i + 1, j - 1) + int(s[i] != s[j])\r\n",
    "    \r\n",
    "        dp = [[0] * k for _ in range(n)]\r\n",
    "        for i in range(1, n):\r\n",
    "            dp[i][0] = cost(0, i)\r\n",
    "            for j in range(1, min(k, i + 1)):\r\n",
    "                dp[i][j] = min(dp[p][j - 1] + cost(p + 1, i) for p in range(j - 1, i))\r\n",
    "        return dp[n - 1][k - 1]\r\n",
    "            \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        # 预处理f[i][j]表示把[i..j]变为回文串的最少修改字符数，之后再跑一个dp枚举分割位置\n",
    "        # f[i][i] = 0\n",
    "        # f[i][i+1] = 1 if s[i] != s[i+1] else 0\n",
    "        # f[i][j] = f[i+1][j-1] + 1 if s[i] != s[j] else f[i+1][j-1]\n",
    "        # i倒序枚举，j正序枚举\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1, n):\n",
    "                f[i][j] = f[i+1][j-1] + 1 if s[i] != s[j] else f[i+1][j-1]\n",
    "        # for x in f:\n",
    "            # print(x)\n",
    "        @cache\n",
    "        def dfs(i, k): # [0..i]\n",
    "            if k < 1: return inf\n",
    "            if k == 1: return f[0][i]\n",
    "            # if i == 0: \n",
    "                # return 0 if k == 1 else inf # 分为k个子串，只需分割k-1次，因此k到1才返回\n",
    "            res = inf\n",
    "            for j in range(i):\n",
    "                res = min(res, dfs(j, k-1) + f[j+1][i])  # [0..i] = [0..j] + [j+1..i]\n",
    "            return res\n",
    "        # print(dfs(3, 2))\n",
    "        return dfs(n-1, k)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(l, r, k):\n",
    "            # if k < 1: return inf\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for end in range(n):\n",
    "            for start in range(end):\n",
    "                if end == start+1:\n",
    "                    dp[start][end] = int(s[start] != s[end])\n",
    "                else:\n",
    "                    dp[start][end] = int(s[start] != s[end]) + dp[start+1][end-1]\n",
    "        @cache\n",
    "        def fun(now, count):\n",
    "            if now == n:\n",
    "                return 0 if count == k else 100\n",
    "            if count > k:\n",
    "                return 100\n",
    "            res = fun(now+1, count+1)\n",
    "            for end in range(now+1, n):\n",
    "                res = min(dp[now][end]+fun(end+1, count+1), res)\n",
    "            return res\n",
    "        return fun(0, 0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        # 预处理f[i][j]表示把[i..j]变为回文串的最少修改字符数，之后再跑一个dp枚举分割位置\n",
    "        # f[i][i] = 0\n",
    "        # f[i][i+1] = 1 if s[i] != s[i+1] else 0\n",
    "        # f[i][j] = f[i+1][j-1] + 1 if s[i] != s[j] else f[i+1][j-1]\n",
    "        # i倒序枚举，j正序枚举\n",
    "        n = len(s)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(i+1, n):\n",
    "                f[i][j] = f[i+1][j-1] + 1 if s[i] != s[j] else f[i+1][j-1]\n",
    "        for x in f:\n",
    "            print(x)\n",
    "        @cache\n",
    "        def dfs(i, k): # [0..i]\n",
    "            if k < 1: return inf\n",
    "            if k == 1: return f[0][i]\n",
    "            # if i == 0: \n",
    "                # return 0 if k == 1 else inf # 分为k个子串，只需分割k-1次，因此k到1才返回\n",
    "            res = inf\n",
    "            for j in range(i):\n",
    "                res = min(res, dfs(j, k-1) + f[j+1][i])  # [0..i] = [0..j] + [j+1..i]\n",
    "            return res\n",
    "        # print(dfs(3, 2))\n",
    "        return dfs(n-1, k)\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(l, r, k):\n",
    "            # if k < 1: return inf\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        cost = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                t = s[i:j+ 1]\n",
    "                diff = 0\n",
    "                for l in range(len(t) // 2):\n",
    "                    if t[l] != t[len(t) - 1 - l]:\n",
    "                        diff += 1\n",
    "                cost[i][j] = diff\n",
    "        # print(cost)\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i > j:\n",
    "                return inf\n",
    "            if i == 0:\n",
    "                return cost[0][j]\n",
    "            res = inf\n",
    "            for t in range(j + 1):\n",
    "                res = min(res, dfs(i - 1, t - 1) + cost[t][j])\n",
    "            return res\n",
    "        \n",
    "        return dfs(k - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, a: int) -> int:\n",
    "        n = len(s)\n",
    "        # val[i][j] 表示s[i:j+1]子串修改为回文串的字符修改数\n",
    "        val = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                l, r = i, j\n",
    "                while l < r:\n",
    "                    val[i][j] += s[l] != s[r]\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i >= n:\n",
    "                return 0 if j == a else inf\n",
    "            res = inf\n",
    "            for k in range(i, n):\n",
    "                res = min(res, f(k+1, j+1) + val[i][k])\n",
    "            return res\n",
    "        \n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def min_modify(t: str) -> int:\n",
    "            l, r = 0, len(t)-1\n",
    "            diff = 0\n",
    "            while l < r:\n",
    "                if t[l] != t[r]:\n",
    "                    diff += 1\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return diff\n",
    "        @cache\n",
    "        def dfs(l: int, c: int) ->int:\n",
    "            if c == 0:\n",
    "                return min_modify(s[l:])\n",
    "            res = n\n",
    "            for r in range(l+1, n-c+1):\n",
    "                res = min(res, min_modify(s[l:r])+dfs(r, c-1))\n",
    "            return res\n",
    "        return dfs(0, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\r\n",
    "        if k == len(s):\r\n",
    "            return 0 \r\n",
    "        # 考虑需要单次划分出尽可能长的回文串\r\n",
    "\r\n",
    "        n = len(s) \r\n",
    "        @cache\r\n",
    "        def cost(i, j):\r\n",
    "            if i >= j:\r\n",
    "                return 0  \r\n",
    "            return cost(i + 1, j - 1) + int(s[i] != s[j])\r\n",
    "        @cache\r\n",
    "        def dfs(i, k):\r\n",
    "            if k == 1:\r\n",
    "                return cost(0, i - 1)\r\n",
    "            if k > i:\r\n",
    "                return inf \r\n",
    "            return min(dfs(j, k - 1) + cost(j, i - 1) for j in range(1, i))\r\n",
    "        return dfs(len(s), k) \r\n",
    "\r\n",
    "            \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def palindromePartition(self, s: str, k: int) -> int:\r\n",
    "        n = len(s) \r\n",
    "        @cache\r\n",
    "        def cost(i, j):\r\n",
    "            if i >= j: return 0  \r\n",
    "            return cost(i + 1, j - 1) + int(s[i] != s[j])\r\n",
    "        @cache\r\n",
    "        def dfs(i, k):\r\n",
    "            if k == 1: return cost(0, i - 1)\r\n",
    "            if k > i: return inf \r\n",
    "            return min(dfs(j, k - 1) + cost(j, i - 1) for j in range(1, i))\r\n",
    "        return dfs(len(s), k) \r\n",
    "\r\n",
    "            \r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
